package data_structure.offer;

import java.util.ArrayList;
import java.util.Stack;

public class ListNode {

    int value;
    ListNode next;

    public ListNode(int value) {
        this.value = value;
    }

    public ListNode() {

    }

    public static ArrayList<Integer> printListNode(ListNode node) {

        ArrayList<Integer> list = new ArrayList<Integer>();
        Stack<ListNode> stack = new Stack<>();
        ListNode headNode = node;
        while (headNode != null) {
            stack.push(headNode);
            headNode = headNode.next;
        }

        while (!stack.isEmpty()) {
            list.add(stack.pop().value);
        }

        return list;
    }

    public static ArrayList<Integer> printListReverse(ListNode node) {

        ArrayList<Integer> list = new ArrayList<>();
        if (node != null) {
            if (node.next != null) {
                list = printListReverse(node.next);
            }
            list.add(node.value);
        }
        return list;
    }

    public static void deleteNode(ListNode head, ListNode deleteNode) {

        if (head == null || deleteNode == null) {
            return;
        }
        if (deleteNode == head) {
            head = null;
        } else {
            if (deleteNode.next == null) {
                ListNode pointer = head;
                while (pointer.next.next != null) {
                    pointer = pointer.next;
                }
                pointer.next = null;
            } else {
                //移花接木
                deleteNode.value = deleteNode.next.value;
                deleteNode.next = deleteNode.next.next;
            }
        }

    }

    public static ListNode findTailNodeK(ListNode head, int k) {

        if (head == null || k < 1) {
            return null;
        }

        ListNode fast = head;
        ListNode slow = head;

        while (k-- > 1) {
            if (fast == null) {
                return null;
            }
            fast = fast.next;
        }

        while (fast.next != null) {

            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    public static ListNode reverseNode(ListNode head, boolean isRecursion) {
        if (!isRecursion) {
            ListNode pre = null;
            ListNode curr = head;

            while (curr != null) {

                ListNode temp = curr.next;
                curr.next = pre;
                pre = curr;
                curr = temp;
            }

            return pre;
        } else {

            if (head == null || head.next == null) {
                return head;
            }

            ListNode p = reverseNode(head.next, true);
            head.next.next = head;//head.next.next=head.next;
            head.next = null;

            return p;
        }

    }

    public static ListNode mergeTwoSortedNodes(ListNode head1, ListNode head2, boolean isRecursion) {
        if (isRecursion) {
            if (head1 == null) {
                return head2;
            }

            if (head2 == null) {
                return head1;
            }

            if (head1.value < head2.value) {

                head1.next = mergeTwoSortedNodes(head1.next, head2, true);
                return head1;
            } else {

                head2.next = mergeTwoSortedNodes(head1, head2.next, true);
                return head2;
            }
        } else {
            if (head1 == null) {
                return head2;
            }
            if (head2 == null) {
                return head1;
            }

            ListNode preHead = new ListNode(-1);
            ListNode pre = preHead;

            while (head1 != null && head2 != null) {

                if (head1.value < head2.value) {
                    pre.next = head1;
                    head1 = head1.next;
                } else {
                    pre.next = head2;
                    head2 = head2.next;
                }
                pre = pre.next;
            }

            pre.next = head1 == null ? head2 : head1;

            return preHead.next;
        }

    }




    public static void main(String[] args) {

        ListNode[] list = new ListNode[10];
        for (int i = 0; i < 10; i++) {
            list[i] = new ListNode(i);
        }

        for (int i = 0; i < 9; i++) {
            list[i].next = list[i + 1];
        }

        ListNode[] list1 = new ListNode[10];
        for (int i = 0; i < 10; i++) {
            list1[i] = new ListNode(i);
        }

        for (int i = 0; i < 9; i++) {
            list1[i].next = list1[i + 1];
        }
        ListNode node = mergeTwoSortedNodes(list[0], list[0], false);
        ArrayList<Integer> nodes = printListNode(list[0]);
        for (int value : nodes) {
            System.out.println(value);
        }
    }
}
